Guía de Estudios de Matemática Discreta – Parcial 4.

PROBLEMA 36

Notación y terminología:

Una sucesión de numeros h(0), h(1), h(2), ..., h(n), ... y una ecuación que relaciona a h(n) con sus predecesores en la sucesión anterior, valida para todos los enteros n mayores que algun entero no se llama relación recursiva.

El factorial de n se define como: n!=1.2.3.4.5...n.

El numero de permutaciones sin repeticion de n objetos es n!.

Antecedentes: El problema ha sido tomado del libro El Arte de Contar o Teoría Combinatoria del Prof José Rodríguez. Ejercicio 1. Capitulo IV.

Problema.

Denotemos por h(n) el numero de maneras de arreglar n objetos distintos en una fila. Encuentre una relación recurrente para .

Solución.

Sabemos que el numero de maneras de arreglar n objetos distintos en una fila es n!. Necesitamos una relación recurrente para la sucesión 1!, 2!, 3!, 4!,..., n!,... Sabemos tambien que n!=n(n-1)!, y esto nos da la relación recursiva requerida:

Con la condición inicial:

Moraleja:

Optar por relaciones recurrentes para resolver problemas de conteo proporciona soluciones naturales e intuitivas en muchas ocasiones.